1707C - DFS Trees - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (ll i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
int T,Q;
string s;
#define Nmax 401010
#define Lmax 20

int pr[Nmax],h[Nmax];
int findx(int x) {
  int R = x, y; while(pr[R] != R) R = pr[R];
  while(pr[x] != x) { y = pr[x]; pr[x] = R; x = y;}
  return R;
}
void unite(int x, int y) {
  x = findx(x); y = findx(y); if (x == y) return;
  if(h[x] > h[y]) { pr[y] = x; h[x] += h[y]; }
  else { pr[x] = y; h[y] += h[x]; }
}

int par[Nmax][Lmax],N,M, lg[Nmax], lvl[Nmax];
vi g[Nmax];
void dfs(int nod, int lev){
  lvl[nod] = lev;
  for(auto x: g[nod])
  if(!lvl[x]) { par[x][0] = nod; dfs(x, lev+1); }
}
int lca(int x,int y){
  if(lvl[x] < lvl[y]) swap(x,y);
  int log1=1, log2=1;
  for(;(1<<log1) < lvl[x]; ++log1);
  for(;(1<<log2) < lvl[y]; ++log2);
  for(int k = log1; k >= 0; --k){
    if(lvl[x] - (1 << k) >= lvl[y]) x = par[x][k];
  }
  if (x == y) return x;
  for(int k=log2; k>=0 ;--k) {
    if(par[x][k] && par[x][k] != par[y][k]){
      x = par[x][k]; y = par[y][k];
    }
  }
  return par[x][0];
}
void preprocessLca() {
  dfs(1,1);
  for(int k=1; (1<<k) <= N; ++k){
    for(int i=1;i<=N;++i){
      par[i][k] = par[par[i][k-1]][k-1];
    }
  }
}

int u1[Nmax], u2[Nmax], val[Nmax];


void df(int x) {
  val[x] = u1[x];
  if (par[x][0] != x) {
    val[x] += u2[par[x][0]];
    val[x] += val[par[x][0]];
  }
  for (auto n : g[x]) {
    if (par[x][0] == n) continue;
    df(n);
  }

}

int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> M;
  vector<pii> gd;
  vector<pii> bd;
  FOR(i, N+10) {
    pr[i] = i;
    h[i] = 1;
  }
  FOR(i, M) {
    int x,y;
    cin >> x >> y;
    if (findx(x) != findx(y)) {
      unite(x,y);
      g[x].pb(y);
      g[y].pb(x);
    } else {
      bd.pb({x,y});
    }
  }
  preprocessLca();
  for (auto x : bd) {
    //cout << x.fs << " " << x.sc << endl;
    int p = lca(x.fs, x.sc);
    //cout << p << endl;
    if (p == x.fs || p ==x.sc) {
      int other = x.fs == p ? x.sc : x.fs;
      int succ = other;
      int l = lvl[other];
      for(int k=20; k>=0 ;--k) {
        if (l - (1 << k)> lvl[p]) {
          succ = par[succ][k];
          l -= (1 << k);
        }
      }

      //cout << x.fs << " " << x.sc << " " << succ << " " << p << " " << other << endl;
      u1[1] += 1;
      u1[succ] -= 1;
      u1[other] += 1;
    } else {
      u1[x.fs]+=1;
      u1[x.sc]+=1;

    }
  }
  df(1);
  for(int i=1;i<=N;++i) {
    //cout << val[i] << endl;
    cout << (val[i] == sz(bd)) ? "1" : "0";
  }
  cout << "\n";

}